<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Kolmogorov-Smirnov Distribution</title>
<link rel="stylesheet" href="../../../math.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../../index.html" title="Math Toolkit 4.2.0">
<link rel="up" href="../dists.html" title="Distributions">
<link rel="prev" href="inverse_gaussian_dist.html" title="Inverse Gaussian (or Inverse Normal) Distribution">
<link rel="next" href="laplace_dist.html" title="Laplace Distribution">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="inverse_gaussian_dist.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../dists.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="laplace_dist.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist"></a><a class="link" href="kolmogorov_smirnov_dist.html" title="Kolmogorov-Smirnov Distribution">Kolmogorov-Smirnov
        Distribution</a>
</h4></div></div></div>
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">math</span><span class="special">/</span><span class="identifier">distributions</span><span class="special">/</span><span class="identifier">kolmogorov_smirnov</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span></pre>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">{</span> <span class="keyword">namespace</span> <span class="identifier">math</span><span class="special">{</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">RealType</span> <span class="special">=</span> <span class="keyword">double</span><span class="special">,</span>
          <span class="keyword">class</span> <a class="link" href="../../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a>   <span class="special">=</span> <a class="link" href="../../pol_ref/pol_ref_ref.html" title="Policy Class Reference">policies::policy&lt;&gt;</a> <span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">kolmogorov_smirnov_distribution</span><span class="special">;</span>

<span class="keyword">typedef</span> <span class="identifier">kolmogorov_smirnov_distribution</span><span class="special">&lt;&gt;</span> <span class="identifier">kolmogorov_smirnov</span><span class="special">;</span>

<span class="keyword">template</span> <span class="special">&lt;</span><span class="keyword">class</span> <span class="identifier">RealType</span><span class="special">,</span> <span class="keyword">class</span> <a class="link" href="../../../policy.html" title="Chapter 22. Policies: Controlling Precision, Error Handling etc">Policy</a><span class="special">&gt;</span>
<span class="keyword">class</span> <span class="identifier">kolmogorov_smirnov_distribution</span>
<span class="special">{</span>
<span class="keyword">public</span><span class="special">:</span>
   <span class="keyword">typedef</span> <span class="identifier">RealType</span>  <span class="identifier">value_type</span><span class="special">;</span>
   <span class="keyword">typedef</span> <span class="identifier">Policy</span>    <span class="identifier">policy_type</span><span class="special">;</span>

   <span class="comment">// Constructor:</span>
   <span class="identifier">kolmogorov_smirnov_distribution</span><span class="special">(</span><span class="identifier">RealType</span> <span class="identifier">n</span><span class="special">);</span>

   <span class="comment">// Accessor to parameter:</span>
   <span class="identifier">RealType</span> <span class="identifier">number_of_observations</span><span class="special">()</span><span class="keyword">const</span><span class="special">;</span>

<span class="special">}}</span> <span class="comment">// namespaces</span>
</pre>
<p>
          The Kolmogorov-Smirnov test in statistics compares two empirical distributions,
          or an empirical distribution against any theoretical distribution.<a href="#ftn.math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f0" class="footnote" name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f0"><sup class="footnote">[1]</sup></a> It makes use of a specific distribution which is informally
          known in the literature as the Kolmogorv-Smirnov distribution, implemented
          here.
        </p>
<p>
          Formally, if <span class="emphasis"><em>n</em></span> observations are taken from a theoretical
          distribution <span class="emphasis"><em>G(x)</em></span>, and if <span class="emphasis"><em>G</em></span><sub><span class="emphasis"><em>n</em></span></sub>(<span class="emphasis"><em>x</em></span>)
          represents the empirical CDF of those <span class="emphasis"><em>n</em></span> observations,
          then the test statistic
        </p>
<div class="blockquote"><blockquote class="blockquote"><p>
            <span class="inlinemediaobject"><img src="../../../../equations/kolmogorov_smirnov_test_statistic.svg"></span>

          </p></blockquote></div>
<p>
          will be distributed according to a Kolmogorov-Smirnov distribution parameterized
          by <span class="emphasis"><em>n</em></span>.
        </p>
<p>
          The exact form of a Kolmogorov-Smirnov distribution is the subject of a
          large, decades-old literature.<a href="#ftn.math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f1" class="footnote" name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f1"><sup class="footnote">[2]</sup></a> In the interest of simplicity, Boost implements the first-order,
          limiting form of this distribution (the same form originally identified
          by Kolmogorov<a href="#ftn.math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f2" class="footnote" name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f2"><sup class="footnote">[3]</sup></a>), namely
        </p>
<div class="blockquote"><blockquote class="blockquote"><p>
            <span class="inlinemediaobject"><img src="../../../../equations/kolmogorov_smirnov_distribution.svg"></span>

          </p></blockquote></div>
<p>
          Note that while the exact distribution only has support over [0, 1], this
          limiting form has positive mass above unity, particularly for small <span class="emphasis"><em>n</em></span>.
          The following graph illustrations how the distribution changes for different
          values of <span class="emphasis"><em>n</em></span>:
        </p>
<div class="blockquote"><blockquote class="blockquote"><p>
            <span class="inlinemediaobject"><img src="../../../../graphs/kolmogorov_smirnov_pdf.svg" align="middle"></span>

          </p></blockquote></div>
<h5>
<a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.h0"></a>
          <span class="phrase"><a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.member_functions"></a></span><a class="link" href="kolmogorov_smirnov_dist.html#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.member_functions">Member
          Functions</a>
        </h5>
<pre class="programlisting"><span class="identifier">kolmogorov_smirnov_distribution</span><span class="special">(</span><span class="identifier">RealType</span> <span class="identifier">n</span><span class="special">);</span>
</pre>
<p>
          Constructs a Kolmogorov-Smirnov distribution with <span class="emphasis"><em>n</em></span>
          observations.
        </p>
<p>
          Requires n &gt; 0, otherwise calls <a class="link" href="../../error_handling.html#math_toolkit.error_handling.domain_error">domain_error</a>.
        </p>
<pre class="programlisting"><span class="identifier">RealType</span> <span class="identifier">number_of_observations</span><span class="special">()</span><span class="keyword">const</span><span class="special">;</span>
</pre>
<p>
          Returns the parameter <span class="emphasis"><em>n</em></span> from which this object was
          constructed.
        </p>
<h5>
<a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.h1"></a>
          <span class="phrase"><a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.non_member_accessors"></a></span><a class="link" href="kolmogorov_smirnov_dist.html#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.non_member_accessors">Non-member
          Accessors</a>
        </h5>
<p>
          All the <a class="link" href="../nmp.html" title="Non-Member Properties">usual non-member accessor
          functions</a> that are generic to all distributions are supported:
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.cdf">Cumulative Distribution Function</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.pdf">Probability Density Function</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.quantile">Quantile</a>, <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.hazard">Hazard Function</a>, <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.chf">Cumulative Hazard Function</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.mean">mean</a>, <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.median">median</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.mode">mode</a>, <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.variance">variance</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.sd">standard deviation</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.skewness">skewness</a>, <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.kurtosis">kurtosis</a>, <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.kurtosis_excess">kurtosis_excess</a>,
          <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.range">range</a> and <a class="link" href="../nmp.html#math_toolkit.dist_ref.nmp.support">support</a>.
        </p>
<p>
          The domain of the random variable is [0, +∞].
        </p>
<h5>
<a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.h2"></a>
          <span class="phrase"><a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.accuracy"></a></span><a class="link" href="kolmogorov_smirnov_dist.html#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.accuracy">Accuracy</a>
        </h5>
<p>
          The CDF of the Kolmogorov-Smirnov distribution is implemented in terms
          of the fourth <a class="link" href="../../jacobi_theta/jacobi_theta_overview.html" title="Overview of the Jacobi Theta Functions">Jacobi
          Theta function</a>; please refer to the accuracy ULP plots for that
          function.
        </p>
<p>
          The PDF is implemented separately, and the following ULP plot illustrates
          its accuracy:
        </p>
<div class="blockquote"><blockquote class="blockquote"><p>
            <span class="inlinemediaobject"><img src="../../../../graphs/kolmogorov_smirnov_pdf_ulp.svg" align="middle"></span>

          </p></blockquote></div>
<p>
          Because PDF values are simply scaled out and up by the square root of
          <span class="emphasis"><em>n</em></span>, the above plot is representative for all values
          of <span class="emphasis"><em>n</em></span>. Note that for present purposes, "accuracy"
          refers to deviations from the limiting approximation, rather than deviations
          from the exact distribution.
        </p>
<h5>
<a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.h3"></a>
          <span class="phrase"><a name="math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.implementation"></a></span><a class="link" href="kolmogorov_smirnov_dist.html#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.implementation">Implementation</a>
        </h5>
<p>
          In the following table, <span class="emphasis"><em>n</em></span> is the number of observations,
          <span class="emphasis"><em>x</em></span> is the random variable, π is Archimedes' constant,
          and ζ(3) is Apéry's constant.
        </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<thead><tr>
<th>
                  <p>
                    Function
                  </p>
                </th>
<th>
                  <p>
                    Implementation Notes
                  </p>
                </th>
</tr></thead>
<tbody>
<tr>
<td>
                  <p>
                    cdf
                  </p>
                </td>
<td>
                  <p>
                    Using the relation: cdf = <a class="link" href="../../jacobi_theta/jacobi_theta4.html" title="Jacobi Theta Function θ4">jacobi_theta4tau</a>(0,
                    2*x*x/π)
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    pdf
                  </p>
                </td>
<td>
                  <p>
                    Using a manual derivative of the CDF
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    cdf complement
                  </p>
                </td>
<td>
                  <p>
                    When x*x*n == 0: 1
                  </p>
                  <p>
                    When 2*x*x*n &lt;= π: 1 - <a class="link" href="../../jacobi_theta/jacobi_theta4.html" title="Jacobi Theta Function θ4">jacobi_theta4tau</a>(0,
                    2*x*x*n/π)
                  </p>
                  <p>
                    When 2*x*x*n &gt; π: -<a class="link" href="../../jacobi_theta/jacobi_theta4.html" title="Jacobi Theta Function θ4">jacobi_theta4m1tau</a>(0,
                    2*x*x*n/π)
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    quantile
                  </p>
                </td>
<td>
                  <p>
                    Using a Newton-Raphson iteration
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    quantile from the complement
                  </p>
                </td>
<td>
                  <p>
                    Using a Newton-Raphson iteration
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    mode
                  </p>
                </td>
<td>
                  <p>
                    Using a run-time PDF maximizer
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    mean
                  </p>
                </td>
<td>
                  <p>
                    sqrt(π/2) * ln(2) / sqrt(n)
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    variance
                  </p>
                </td>
<td>
                  <p>
                    (π<sup>2</sup>/12 - π/2*ln<sup>2</sup>(2))/n
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    skewness
                  </p>
                </td>
<td>
                  <p>
                    (9/16*sqrt(π/2)*ζ(3)/n<sup>3/2</sup> - 3 * mean * variance - mean<sup>2</sup> * variance)
                    / (variance<sup>3/2</sup>)
                  </p>
                </td>
</tr>
<tr>
<td>
                  <p>
                    kurtosis
                  </p>
                </td>
<td>
                  <p>
                    (7/720*π<sup>4</sup>/n<sup>2</sup> - 4 * mean * skewness * variance<sup>3/2</sup> - 6 * mean<sup>2</sup> * variance
                    - mean<sup>4</sup>) / (variance<sup>2</sup>)
                  </p>
                </td>
</tr>
</tbody>
</table></div>
<div class="footnotes">
<br><hr style="width:100; text-align:left;margin-left: 0">
<div id="ftn.math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f0" class="footnote"><p><a href="#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f0" class="para"><sup class="para">[1] </sup></a>
            <a href="https://en.wikipedia.org/wiki/Kolmogorov%%&amp;&amp;%upSmirnov_test" target="_top">Wikipedia:
            Kolmogorov-Smirnov test</a>
          </p></div>
<div id="ftn.math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f1" class="footnote"><p><a href="#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f1" class="para"><sup class="para">[2] </sup></a>
            <a href="https://www.jstatsoft.org/article/view/v039i11" target="_top">Simard, R.
            and L'Ecuyer, P. (2011) "Computing the Two-Sided Kolmogorov-Smirnov
            Distribution". Journal of Statistical Software, vol. 39, no. 11.</a>
          </p></div>
<div id="ftn.math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f2" class="footnote"><p><a href="#math_toolkit.dist_ref.dists.kolmogorov_smirnov_dist.f2" class="para"><sup class="para">[3] </sup></a>
            Kolmogorov A (1933). "Sulla determinazione empirica di una legge
            di distribuzione". G. Ist. Ital. Attuari. 4: 83–91.
          </p></div>
</div>
</div>
<div class="copyright-footer">Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland,
      Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno
      Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde,
      Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle
      Walker and Xiaogang Zhang<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="inverse_gaussian_dist.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../dists.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="laplace_dist.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
